#include "stdafx.h"
#include "CppUnitTest.h"

using namespace Microsoft::VisualStudio::CppUnitTestFramework;
namespace NavtiveTest_Question25
{
	typedef struct node{
		int val;
		node* Next;
	} node;

	node* Init(int* a, int n, int m)
	{
		node* head = NULL;
		node* data = NULL;
		node* tmp = NULL;
		for (int i = 0; i < n; i++)
		{
			node* tn = new node();
			tn->val= a[i];
			tn->Next = NULL;
			if(i == m)
			{
				tmp = tn;
			}
			if(i == 0) { head = tn; data = tn;}
			else { data->Next = tn, data = tn;}
		}

		data->Next = tmp;
		return head;
	}

	node* loopstart(node *head){
		node* result = NULL;
		node* fast = head,* slow = head;
		while (fast->Next != NULL)
		{
			fast = fast->Next->Next;
			slow = slow->Next;
			if(fast == slow) break;
		}

		//2*(x+y)=x+2y+z  => x=z
		slow = head;
		while( fast!= slow && fast)
		{
			fast = fast->Next;
			slow = slow->Next;
		}
		result = fast;
		return result;
	}
}
namespace NativeTest
{
	using namespace NavtiveTest_Question25;
	TEST_CLASS(Question25)
	{
	public:

		TEST_METHOD(Question25_TestMethod1)
		{
			int n = 10;
			int a[] = {
				3, 2, 1, 3, 5, 6, 2, 6, 3, 1 
			};
			node* head = loopstart(Init(a, 10, 9));
			Assert::AreEqual(1, head->val);

			head = loopstart(Init(a, 10, 3));
			Assert::AreEqual(3, head->val);
		}
	};
}